/**
 * 
 */

/**
 * @author 
 * Yannic Remmet			196983
 * Tobias Trabelsi			197112
 * Anna-Katharina Wickert	197122
 */
public class SearchTree<T extends Comparable<T> > extends BinaryTree<T> {
	SearchTree() {
		super();
	}
	SearchTree(TreeNode<T> t){
		super(t);
	}
	public boolean insert(T o){
		if (test)
			System.out.println("in inser(T o) : getRoot: " + getRoot());
		return insert(o, getRoot());
	}
	
	private boolean insert(T o, TreeNode<T> t){
		if (test) 
			System.out.println("Beginning of insert(o, t): t.getKey: " + t.getKey() + " o: " + o + " t.getRight() " + t.getRight() + " t.getLeft() " + t.getLeft());
		/*if (t.getKey() == null) {
			t.setKey(o);
			return true;
		} */
		if (o == null)
			return false;
		if (test) {
			System.out.print("t.getKey() == o : ");  System.out.println(t.getKey() == o);
		}
		if (t.getKey() == o) {
			if (test)
				System.out.println("in if t.getKey() == o");
			return false; 
		}
		if (test){
			System.out.println("before if - else (rekursive) t.getRight(): " + t.getRight() + " t.getLeft() " + t.getLeft() + " t.getKey() " + t.getKey() + " o: " + o + " t.getKey().compareTo(o) " + t.getKey().compareTo(o));
			if (testdetails){
				System.out.println("t.getRight: " + t.getRight());
				System.out.println("t.getLeft: " + t.getLeft());
				System.out.println("t.getKey: " + t.getKey());
				System.out.println("o: " + o);
				System.out.println("t.getKey().compareTo(o) " + t.getKey().compareTo(o));
			}
		}
		if (t.getKey().compareTo(o) > 0){
			if (test){
				if (testdetails){
					System.out.println(("t.getRight(): " + t.getRight()));
					System.out.println("o: " + o);
				}
				System.out.println("in if t.getRight(): " + t.getRight() + " o: " + o);
			}
			if (t.getRight() == null){
				if (test)
					System.out.println("in t.getRight()  == null");
				TreeNode<T> res = new TreeNode<T>(o);
				t.setRight(res);
				return true;
			}
			else {
				return insert(o, t.getRight());	
			}
		}
		else {
			if (test)
				System.out.println("in else t.getLeft(): " + t.getLeft() + " o: " + o);
			if( t.getLeft() == null){
				if (test)
					System.out.println("in t.getLeft() == null");
				TreeNode<T> res = new TreeNode<T>(o);
				t.setLeft(res);
				return true;
			}
			else {
				return insert(o, t.getLeft());	
			}
		}

	}
	
	public int level(T o) {
		int level = 0;
		if (o == null)
			return -1;
		TreeNode<T> t = getRoot();
		while(t != null && o != t.getKey()){
			if (t.getKey().compareTo(o) > 0) {
				t = t.getRight();
			}
			else {
				t = t.getLeft();
			}
			level++;
		}
		return level;
	}
	
	public TreeNode<T> findParent(T x){
		TreeNode<T> t = getRoot();
		TreeNode<T> parent = t;
		if (x == null)
			return null;
		if (t == null)
			return null;
		if (test)
			System.out.println("t.getKey(): " + t.getKey() + " parent: " + parent);
		while(t.getKey() != x) {
			parent = t;
			if (t.getKey().compareTo(x) >0)
				t = t.getRight();
			else
				t = t.getLeft();
			if (t == null)
				return null;
		}
		return parent;
			
	}
	
	private TreeNode<T> find (T x) {
		TreeNode<T> help = getRoot();
		if (x == null || x == null)
			return null;
		while (help.getKey() != x) {
			help = (help.getKey().compareTo(x) > 0) ? help.getRight() : help.getLeft();
		if (help == null)
			return null;
		}
		return help;		
	}
	

	
	public boolean delete(T x){
		TreeNode<T> parent = findParent(x);
		TreeNode<T> xNode = find(x);
		if (xNode == null){
			return false;
		}
		if (test)
			System.out.println("parent " + parent + " xNode " + xNode + " xNode.l " + xNode.getLeft() + " xNode.r " + xNode.getRight() +" p=x " + (parent == xNode) + " (parent == xNode && xNode.getLeft() == null && xNode.getRight() == null) " + (parent == xNode && xNode.getLeft() == null && xNode.getRight() == null));
		if (parent == xNode && xNode.getLeft() == null && xNode.getRight() == null){
			if (test)
				System.out.println(" in if xNode = null ");
			xNode = null;
			setRoot(xNode);
			if (test)
				System.out.println(" xNode==null "+ (xNode==null));
			return true;
		}

		if (xNode.getLeft() == null || xNode.getRight() == null) { // Putting next element up 
			return delete1(xNode, parent);
		}
		else { // Putting min up.
			return delete2(xNode,parent);
		}
	}
	
	private boolean delete1(TreeNode<T> x, TreeNode<T> p){
		if (p.getKey().compareTo(x.getKey()) > 0)
			p.setRight(x.getRight());
		else
			p.setLeft(x.getLeft());
		return true;
	}
	
	private boolean delete2(TreeNode<T> x, TreeNode<T> p){
		TreeNode<T> min = searchMin(x.getRight());
		p = findParent(min.getKey());
		x.setKey(min.getKey());
		return delete1(min, p);
	}
	
	private TreeNode<T> searchMin(TreeNode<T> a) {
		if (a == null)
			return a;
		while(a.getLeft() != null)
			a = a.getLeft();
		return a;
	}
	
	boolean test = true;
	boolean testdetails = false;
}
